//实验二  存储管理模拟（一）

#include<stdio.h>
#include<stdlib.h>
#define RAM_Size 640;
enum state{ Wait = 1,Ready = 2 ,Run = 3, Finish = 4};
typedef struct partition{
    struct partition *pre;//前指针
    struct partition *next;//后指针
    int Size;//分区大小
    int Start;//起始地址  
    int partitionState;//分区状态 0 busy 1 free
}Partition;
typedef struct work{
    int  workId;//作业编号
    struct work *next;//后指针
    int needSiez;//分区大小
    int start;//起始地址;
    Partition *address;//指向的地址
}work;
Partition *ListHead;
void printRAM_Info(Partition *List)
{
    Partition *p = List->next;
    printf("编号\t\t内存大小\t\t\t起始地址\t\t\t状态\n");

    int i=1;
    while(p)
    {
        printf("%d\t\t %d\t\t\t %d\t\t\t",i++,p->Size,p->Start,p->partitionState);
        if(p->partitionState == 0)
        {
            printf("Busy\n");
        }
        else{
            printf("Free\n");
        }
        p = p->next;
    }
}
Partition *inisRAM(void)
{
    Partition *List =(Partition *) malloc(sizeof(Partition));

    Partition *Init =(Partition *) malloc(sizeof(Partition));
    List->partitionState = -1;
    Init->next = NULL;
    Init->pre = List;
    Init->Size = RAM_Size;
    Init->Start = 0;
    Init->partitionState = 1;
    List->next = Init;
    return List;
}


void orderBySize(Partition *List)
{
//    冒泡排序
    Partition *f, *p, *x, *y;
            f = NULL;
            if(List -> next == NULL || List -> next -> next == NULL)
            {
                return;
            }
            while(f != List->next->next)
            {
                for(p = List; p -> next -> next != f; p = p -> next)
                {
                        if(p -> next -> Size > p -> next -> next ->Size )
                    {
                        x = p -> next;
                        y = p -> next -> next;

                        p -> next = y;
                        y->pre = p;

                        x -> next = y -> next;
                        if(y->next!=NULL)
                            y->next->pre = x;

                        y -> next = x;
                        x -> pre = y;
                    }

                }
                f = p -> next;
            }
}
Partition *first_fit(work *w,Partition *L)
{
//    orderByAddress(L);
    Partition *new = (Partition *) malloc(sizeof(Partition));
    Partition *p = L->next;

    new->Size = w->needSiez;
    new->partitionState = 0;



    while(p)
    {
//        printf("*************\n");
//        printf("w = %d\n",w->needSiez);
//        printf("p - %d\n",p->Size);
//        printf("p - %d\n",p->partitionState);
        if(p->partitionState == 1 && p->Size == w->needSiez)
        {
        
            p->Size = 0;
            p->partitionState = 0;
            w->address = p;
            w->start = p->Start;
            p->Start += w->needSiez;
            printf("内存分配成功！！！\n");
            break;

        }
        else if(p->partitionState == 1 && p->Size > w->needSiez)
        {
            
//            w->address = p;
//            p->Size -= w->needSiez;
//            w->start = p->Start;
//            p->Start += w->needSiez;
            new->next = p;
            new->pre = p->pre;
            p->pre->next = new;
            p->pre = new;
            new->Size = w->needSiez;
            new->partitionState = 0;
            p->Size -= w->needSiez;
            w->address = new;
            new->Start = p->Start;
            p->Start = new->Start+new->Size;
            w->start = new->Start;
            printf("内存分配成功！！！\n");
            break;
        }
        p = p->next;
    }
    return L;
}
Partition *best_fit(work *w,Partition *List)
{
//    orderBySize(List);
    Partition *new = (Partition *) malloc(sizeof(Partition));
    Partition *p = List->next;
//    printf("排序后");
//    printRAM_Info(List);

    new->Size = w->needSiez;
    new->partitionState = 0;
    int minGrap = 99999;//记录最小差值，差值最小的就说明最适合分配
    Partition *best = NULL;
    while(p)
    {
        if(p->partitionState == 1 && p->Size == w->needSiez)
        {
            p->Size = 0;
            p->partitionState = 0;
            w->address = p;
            w->start = p->Start;
            p->Start += w->needSiez;
            printf("内存分配成功！！！\n");
            best = NULL;
            break;
        }
       else  if(p->partitionState == 1 && p->Size > w->needSiez)
        {
            int grap = p->Size - w->needSiez;
            if( grap < minGrap)
            {
                minGrap = grap;
                best = p;
            }
           
        }
        p = p->next;
    }
    if(best != NULL)
    {
        new->next = best;
        new->pre = best->pre;
        best->pre->next = new;
        best->pre = new;
        new->Size = w->needSiez;
        new->partitionState = 0;
        best->Size -= w->needSiez;
        w->address = new;
        new->Start = best->Start;
        best->Start = new->Start+new->Size;
        w->start = new->Start;
        printf("内存分配成功！！！\n");
    }
    return List;
}
void freeRAM(work *w,Partition *List)
{

//    printf("id= %d\n",w->address->Size);

    Partition *p = List->next;
//    printf("size%d",p->Size);
    while(p)
    {

        if(w->address == p)
        {
//            printf("id");
//            printf("--%d",p->pre->partitionState);
//            p->Size += w->needSiez;
//            p->Start += w->needSiez;

            if(p->pre->partitionState == 1 && p->next->partitionState == 0)
            {
                
                Partition *front = p->pre;
                p->next->pre = front;
                front->next = p->next;
                front->Size += p->Size;
                front->partitionState = 1;
                free(p);
            }
           else  if( p->next->partitionState == 1 && p->pre->partitionState == 0)
            {
                Partition *temp = p->pre;
//                p->next->pre = front;
//                front->next = p->next;
//                front->Size += p->Size;
                    temp->next = p->next;
                    p->next->pre = temp;
                    p->next->Size += p->Size;
                    p->next->partitionState = 1;
                    p->next->Start = p->Start;
                    free(p);
            }
           else if(p->next->partitionState == 1 && p->pre->partitionState == 1)
            {
                Partition *front = p->pre;
                front->next = p->next->next;
                if(p->next->next!=NULL)
                    p->next->next->pre = front;
                front->Size = p->Size + front->Size + p->next->Size;
                front->partitionState = 1;
                free(p->next);
                free(p);
            }
           else if(p->next->partitionState == 0 && p->pre->partitionState == 0)
            {
                p->partitionState = 1;
            }
            else if(p->pre->partitionState == -1 && p->next->partitionState == 0 )
            {
                printf("4");
                p->partitionState = 1;

            }
            else if(p->pre->partitionState == -1 && p->next->partitionState == 1 )
            {
                printf("5");
                p->Size += p->next->Size;
                p->partitionState = 1;
                p->next = p->next->next;
                p->next->next->pre = p;
                free(p->next);

            }

            else if(p->pre->partitionState == 0 && p->next == NULL)
            {
                printf("6");
                p->partitionState = 1;
            }
            else if(p->pre->partitionState == 1 && p->next == NULL)
            {
                printf("7");
                p->Size += p->pre->Size;
                p->Start = p->pre->Start;
                p->partitionState = 1;
                p->pre = p->pre->next;
                p->pre->pre->next = p;
                free(p->pre);
            }
            break;
        }
        p = p->next;
    }
    printf("回收成功！\n");
}


work * initWork(work *head)
{
    head =(work *) malloc(sizeof(work));
    head->next=NULL;
    return head;
}
work * createWork(work *head,Partition *ListHead)
{
    int input;
    work *end = head;

    printf("请输入你要创建作业的数量:");
    scanf("%d",&input);
    for(int i=0;i<input;i++)
    {
        work *new =(work *) malloc(sizeof(work));
        printf("请输入作业编号:");
        scanf("%d",&new->workId);
        printf("请输入申请空间大小:");
        scanf("%d",&new->needSiez);
        printf("作业创建成功！！！\n");
        new->address = 0;
        printf("提示：两种算法不能混合分配！每次执行只能使用一种算法！换算法需要重新运行！");
        printf("\n请输入你要执行的算法:1.首次适应算法 2.最佳自适应算法:");
        int c;
        scanf("%d",&c);
        if(c == 1)
            {
                printf("首次适应算法\n");
            ListHead = first_fit(new,ListHead);//分配内存
            }

        else if(c== 2)
            {
                printf("最佳自适应算法\n");
            ListHead = best_fit(new,ListHead);//分配内存
            }
        while(end)
        {
            if(end->next==NULL)
            {
                end->next = new;
                new->next =NULL;
                break;
            }
            end = end->next;
        }

    }
    return head;
}
void showWork(work *head)
{
    work *p = head->next;
    printf("作业编号\t\t");
    printf("占用内存\t\t");
    printf("起始地址\t\t");
    printf("\n");
    while (p) {
        printf("\t%d \t\t  %d \t\t  %d\n",p->workId,p->needSiez,p->start);
        p = p->next;
    }
}
void deleteWork(work *w,work *h)
{
    work *p = h->next;
    if(w == p)
    {
        h->next = w->next;
        free(w);
        return;
    }
    while(p)
    {
        if(p->next == w)
        {
            p->next = w->next;
            free(w);
            break;       
        }
        p = p->next;
    }
}
int main()
{
    Partition *ListHead = inisRAM();
    work *headWork = initWork(headWork);
    int choose;
    do{
        printf("*******************\n");
        printf("1.创建作业并申请内存\n");
        printf("2.查看作业\n");
        printf("3.作业取消(内存释放)\n");
        printf("4.查看内存情况\n");
        printf("0.退出");
        printf("请输入你的选择:");
        scanf("%d",&choose);
        if(choose == 1)
        {

            headWork = createWork(headWork,ListHead);

        }
        else if(choose == 2)
        {
            printf("查看作业\n");
            showWork(headWork);
        }
        else if(choose == 3)
        {
            work *w = headWork->next;
            int id;
            showWork(headWork);
            printf("请输入你要结束的作业的id:");
            scanf("%d",&id);
            while(w)
            {
                if(w->workId == id)
                    break;
                w = w->next;
            }
            freeRAM(w,ListHead);
            deleteWork(w,headWork);
        }
        else if(choose == 4)
        {
//            orderBySize(ListHead);
            printRAM_Info(ListHead);
        }
    }while(choose!=0);

}

